#ifndef _SOKOBAN_CBOARD_H_
#define _SOKOBAN_CBOARD_H_

#include "constants.h"
#include "macro.h"
#include "cmovepool.h"
#include <stdint.h>
#include <string>
#include <stdio.h>
#include <vector>
#include <cassert>
#include <array>
#include <unordered_set>

namespace sokoban {

/* forward declarations */

///represents a position in an nxn board
class CBoard
{
  private:

    // board stored as an array using *row-wise* indexes.
    static ECell  * mCell;

    // position of the goals on the board
    static T_POS * goalsCells;

    static uint8_t  nBoxes;
    static T_DIM  nRow;
    static T_DIM  nCol;

    // manhattant distance between each of the cells on the board. -1 for a
    // cell means this cell cannot be reach
    static uint16_t * distances;

    static bool originBoardCreated;

  public:

    // construct a board from its representation as a string
    // the cells that are reachable for the player are also computed and stored in playerMoves
    explicit CBoard( std::string & stringBoard );

    CBoard( CBoard const & other );

    /// constructs a board which is the result of applying move \p pMove to board \p pRH
    /// \param pRH the starting board position
    /// \param pMove the movement to perform
    ///
    /// \sa DoMove()
    CBoard(const CBoard &pRH, const CBoxMove &pMove);

    // Destructor
    ~CBoard();

    ///returns the content of a cell in the board.

    /// this function returns a byte representing the contents of the cell,
    /// using the enumeration values in ECell
    ///
    /// TODO right now if there is a box it wont be returned. Is it ok ?
    ECell At( T_POS pPos ) const
    {
      ASSERT( pPos > ( nCol * nRow ), "Accessing out of bound board data" );

      return mCell[ pPos ];
    }

    ///operator version of the above function
    ECell operator()(T_POS pPos) const
    {
      return At(pPos);
    }

  public:

    /// returns a list of all valid moves
    /// \param pMoves a vector where the list of moves will be appended
    void FindPossibleBoxesMoves(std::vector<CBoxMove> & pMoves) const;

    ///transforms the board by performing a move
    ///it doesn't check that the move is valid, so you should only use
    ///it with moves returned by FindPossibleBoxesMoves
    /// \param pMove the move to perform
    void DoMove(const CBoxMove &pMove);

    ///prints the board
    /// This prints the board using ASCII characters (no fancy colors)
    void Print( const std::vector<T_POS> & markers = std::vector<T_POS>() ) const;
    
    ///have all the boxes been correctly placed on the goals?
    bool IsSolution() const;

    /// getter for the member path
    std::string GetPath() const { return path; }

    /// hash function for a board
    /// returns a value based on the position of the boxes and the reachable area of the
    /// player
    uint64_t Hash() const;

    /// Checks if the a new box movement will lead into a dynamic deadlock
    /// \param uint16_t newBoxPos position where the box would be moved
    bool DetectDynamicDeadlock( T_POS newBoxPos , uint8_t boxIdx ) const;

    // Is the current state a freeze deadlock? Info on freeze deadlocks at the wiki
    bool IsFreezeDeadlock() const;

    bool FormsBlockDeadlock( T_POS newBoxPos ) const;

    // return the value of the board (computed heuristic)
    uint16_t Value() const;

    bool operator<( CBoard const & boardOther ) const;

  protected:

    // populate the matrix holding distance between each of the
    // cells of the board, using manhattan distance
    void computeManhattanDistances();

    // populate the matrix holding distance between each of the cells of
    // the board, using djikstra shortest path algo
    void computeDjikstraPath();

    // compute and return the heuristic associated with the board (based on
    // the manhattan distance)
    void computeHeuristic();

    // Find static deadlocks in the board and mark them in the mCell array.
    void findStaticDeadlocks();

    void findStaticDeadlocksBis();

    // Function used in findStaticDeadlocks to pull a box through the board.
    void pullBoxBFS( bool reachedCells[], T_POS initBoxPos );

    // Function used in pullBoxBFS to find the possible cells where the box can be pulled.
    void findPossiblePullMoves( T_POS boxPos, std::vector<T_POS> & possibleMoves );

    // Find all the positions the player can reach in the board
    // **without moving any box**
    void findCharacterReachablePos
    (
      T_POS from,
      EMoveElem fromMove,
      CMovePool * movesAlreadyDone
    ) const ;

    // Calls the function findCharacterReachablePos to populate in playerMoves the info about
    // the cells that the player can reach
    // This method must be called in the constructors of CBoard
    void storeCharacterReachablePos();

    // Obtains the cell with minimum index (top left-most cell) that the player can reach
    uint16_t getMinimumReachablePos() const;

    // Find all the cell directly adjacent to fromPos and that are walkable
    uint8_t tryElemMoves( T_POS fromPos, std::array< EMoveElem, 4 > & nextMoves ) const ;

    /// Can an element of the game go to position?
    /// \param EWHO     who     PLAYER or BOX to be moved
    /// \param uint8_t  boxIdx  index in boxCells if is a box to be moved
    bool isFreeFor( T_POS position , EWHO who , uint8_t boxIdx = 0 ) const;

    bool isGoal( T_POS cell ) const;

    bool isBoxFrozenHor( T_POS boxPos, std::unordered_set< T_POS > & visitedCells ) const;

    bool isBoxFrozenVer( T_POS boxPos, std::unordered_set< T_POS > & visitedCells ) const;

    bool isBox( T_POS cell ) const;

  private:

    // heuristic associated with the board
    uint16_t    value;

    // position of the player's cell on the grid.
    T_POS    playerCell;

    // positions of the boxes on the board
    T_POS  * boxesCells;

    // accesible cells for the player in this state
    CMovePool * playerMoves;

    // movements done by the player to reach this state from the initial
    // board configuration
    std::string path;

};

/*namespace sokoban*/ }

#endif
